The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet. Each packet is typically part of a larger set of information being communicated between two entities, and it is desirous and often a requirement that packets of a sequence be delivered in the order specified by that sequence. However, various transmission, packet processing, and packet switching techniques may result in packets arriving out of order at intermediate or final destinations where the packets are needed in their original order. Thus, a packet resequencing technique must be employed, such as storing the packets in random access memory and removing them from the memory in order.
Similarly, a single packet can be split into multiple packet fragments for transmission, processing or other purposes. For example, Multilink Point-to-Point Protocol (MLPPP) and Frame Relay Forum 0.12 (FRF 0.12) break a packet into fragments and transmit these multiple packet fragments over multiple physical links or facilities. These packets fragments are each identified with a packet sequence number to identify the order of the fragments. The receiving device must then reassemble the original packets in order from the received packet fragments as well as detect and recover from any lost packet fragments. One feature that makes this packet reassembly and error detection easier is that packets received over one of the links will, in the most prevalent uses of reassembly, also include a monotonically increasing link sequence number for the corresponding link over which the packet fragment is received or for the set of links over which the packet fragments are received. Although these packet fragments may often be received in order, there are situations for which some of these packet fragments may be received out of order.
Known systems performing packet reassembly use random access memory to reassemble the packets. For example, one technique writes each of the received packet fragments in memory at any location and keeps track of the received fragments and their location in memory in a “scorecard” data structure (e.g., it indicates the memory locations in reassembly order). Based on the scorecard, the packet fragments can be read out of memory in order to reassemble the original packet.
Another known technique allocates a portion of memory large enough to handle a largest size packet, and then stores each packet fragment in this portion of memory at a position relative to the sequence number of the fragment. In this manner, a packet is reassembled in memory, and the contiguous memory locations can be read to generate the reassembled packet.
In another context, merge sorting is a known technique for producing a single sorted list from multiple ordered lists whose values are known a priori. For example, two lists of known elements sorted in ascending order can be combined into a single sorted list by repeatedly taking the smaller value from the front of lists, and appending the smaller value to the end of the combined list. This example can be extended to a set of n known values, which can be sorted by first dividing the set into n lists containing a single value each, then combining pairs of lists to produce n/2 lists with two values each. Pairs of these lists are then merged, producing n/4 lists with four values each. Continuing in this fashion eventually yields a single sorted list containing the original values, but in sorted order. Merge sorting can also be implemented using three-way merging (that is, merging three sorted lists into a single sorted list in one step), rather than by using two-way merging. More generally, d-way merging can be used for any integer d>1. However, merge sorting cannot be used to produce a merged list of items by merging lists where one or more of the lists is not already in sorted order, as the merging technique can only take an item from the front of an input list, and not a next item in order that is not at the front of one of the input lists.